The present invention generally relates to improvements to computer technology and particularly to compilers for improving the efficiency of computer programs by informing restructuring code using iteration-point algebraic difference analysis.
Computer systems have evolved into extremely sophisticated devices, and computer systems may be found in many different settings. Dramatic advances in both hardware and software (e.g., computer programs) have drastically improved the performance of computer systems. Modern software has become very complex when compared to early computer programs. Many modern computer programs have tens or hundreds of thousands of instructions. The execution time (and hence, performance) of a computer program is very closely related to the number of instructions that are executed as the computer program runs. Thus, as the size and complexity of computer programs increase, the execution time of the computer program increases as well.
Restructuring of loop code is a transformation of computer programs attempted by optimizing compilers. A requirement for most any such transformation is a dependence analysis—a process that computes dependences both within and across loop iterations with the goal of determining relationships between program statements in a loop. Program-statement dependence information is essential when restructuring loop code both to speculate on the performance impact of such transformations as well as to ensure that the semantics of the original program are preserved. Dependence analysis is an integral part of any industrial-strength optimizing compiler. Compilers typically use a sequential series of refinements to a data dependence graph though multiple different techniques. Such organization is well suited for the addition of new, more powerful, analysis techniques over time to get even more precision.